{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Classification with K-Nearest Neighbours\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generate some training and testing data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXMAAAEACAYAAABBDJb9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3W2QXFd5J/D/09ZaMxcCH0KKZCMLQayWhQp1t7oEmzKM\n2rAGx0kcWZg1CJvAgC1t0FizXrNO4oCGrVBFDCHSvlRFjj1CtqXI1kyZkF1e7KzVGiCBUb+M5Bkk\nt9aJR3bWuLJbWSh2LDF0P/uhu2d6evrl9r237+v/V9WlmZ7ue8/t0Tx9+jnPOUdUFUREFGwxrxtA\nRET2MZgTEYUAgzkRUQgwmBMRhQCDORFRCDCYExGFwBonDiIiLwL4MYAKgEVVfacTxyUiInMcCeao\nBvGMqv6zQ8cjIqIeOJVmEQePRUREPXIqACuAZ0TkjIjc5dAxiYjIJKfSLNer6isi8kuoBvXzqvpd\nh45NRERdOBLMVfWV2r//JCJPAXgngBXBXES4CAwRkQWqKt0eYzvNIiKGiLy+9vXrALwfwGybBvnq\nduDAAc/bEIQ2+bVdbBPbFIV2meVEz/zNAJ6q9bzXADimqk87cFwiIjLJdjBX1X8AkHSgLUREZFGk\nywkzmYzXTVjFj20C/Nkutskctsk8v7bLDOklJ2PrRCLq1rmIiMJCRKBuDIASEZH3GMyJiEKAwZyI\nKAQYzImIQoDBnIgoBBjMiYhCwKmFtogCp1KpoFgsAgBSqRRiMfZtKLj4v5ciqVicQzo9iqGheQwN\nzSOdHkWxOOd1s4gs46QhipxKpYJ0ehQzMwex3J+pIJkcRT5/kD108hVOGiJqo1gsolTKYOV//xhK\npR1LaReioGEwJyIKAQZzipxUKoV4PIvqPuR1FcTjp5FKpbxpFJFNzJlTJBWLcxgePoxSaQcAYOPG\nLI4c2YtUaovHLSNayWzOnMGcIisKpYlRuMawYzAnirjlTx8ZAEA8nsX4+B5++ggYBnOiCGP5ZXiw\nNJEowlh+GT2OBXMRiYlIQUS+7tQxiYjIHCd75vsB/NDB4xGRRSy/jB5HgrmIrANwM4CHnTgeEdkT\ni8UwPr4HyeQoDGMShjGJRGI/xsf3MF8eUo4MgIrISQBfAPBGAP9eVW9p8RgOgBK5jKWJwWd2ANT2\nErgi8psAXlXVGRHJAOh6UiJyRywWQzqd9roZ5AIn1jO/HsAtInIzgEEAvyAij6rqx5ofODY2tvR1\nJpNBJpNx4PREROGRzWaRzWZ7fp6jdeYisgNMsxAROYZ15kREEcIZoEREPsaeORFRhDCYExGFAIM5\nEVEIOFGaSBQZnIRDfsX/iUQmFYtzSKdHMTQ0j6GheaTToygW57xuFhEAVrMQmcL1wckrrGYhchDX\nBye/YzAnIgoBBnMiE7g+OPkdc+ZEJi1vkLwDALBx4yl85jM7cN11b2NlC/UNN3Qm6oN6aeKFCy/g\nS1/6Di5evAEAd76n/mEwJ+oTVraQm1jNQtQnrGwhP2IwJyIKAQZzoh6xsoX8iDlzIgtWV7ZkceTI\nXg6AkuM4AErUZ1x0i9zAYE5EFAJmgzmXwCUKOX6CiAbbv1URWSsiPxCRoog8JyIHnGgYEdnHZXuj\nw5E0i4gYqrogIlcB+B6Ae1R1uukxTLMQuYiTm8LB1UlDqrpQ+3ItqqkbRm0ij3FyU7Q4EsxFJCYi\nRQA/AvCMqp5x4rhERGSOIwOgqloBkBKRNwD4moi8XVV/2Py4sbGxpa8zmQwymYwTpyeiFqqTm45i\nZmYnGtMs1clNt3rZNOogm80im832/DzHSxNF5LMA/p+qfqXpfubMiVzGyU3B51qduYi8CcCiqv5Y\nRAYBfBvAF1X1G02PYzCnQAp6aV/Q2x91bgbzdwA4iurnuBiAJ1T1Cy0ex2BOgbPcs80A4Lrl5D7O\nACWyiaV9wRS2TyJcz5zIJpb2BU+UJ0lxOj8RhUKlUsHw8OEVn6RmZnZieDgan6TCfXVENnDd8mCJ\n+icp9szJlrDlJ4GV1/Tww3fhU58aXVHaNz6+1/HrDOPrSO7iAChZFsZKj1bX9PDDdwH4GYD+BNp8\n/jns3v0FXLqUhshbsWnTVOBfRy+EdcDa7AAoVNWVW/VUFBblclmTyREFygpo7Va9r1wue908S7y4\nplzunA4O3qrAhAKTCowocC7Qr6OXCoVZTSZH1DAm1DAmNJHYp4XCrNfNsqUWO7vGWPbMyZJ8Po+h\noXksLOxacb9hTGJqagPS6bRHLbPO7WuqVCrYvPlulEoPobEnCYxicPA9+M533hbI19FrYUtZcXMK\nIp8rFou4dOkDaB6wA3ZA9QUAb/OmYQEXi8Ui+SYY7Lcs8kwYKz28uKbWvUbF+vWFwL6O5A0Gc7Ik\nFothfHwPkslRGMYkDGMSicR+jI/vCezHWrPXVKlUkM/nkc/nUalUOhyxs+qbx2k0v3kMDBzH8eMP\nBPZ1JG8wZ062hC0/CXS+JqcreJaPN4RKpYJrrvk2/vIvR5FOv8PuZVBIcG0WIof1q/QtjG+I5BwG\nc6IemAmoYazgIf/jQltEJkV5cSYKD/bMKdJ6SZ2EdYYh+Rt75kQm9LI4UxgreCg8OGmIqAep1Bbk\n8wcb8uuHGMjJF5hmoUhrlzpJJPajUGCgJu8xzUJkQj11Eo/vhchxAE9A5Hfx2ms/xtmz571uHpFp\ntoO5iKwTkWdFZE5EnhORe5xoGFE/tJq9mUhsxuDgWqhuBHAtVI+iVPoqhocPm5rhaWdGqFOzSYmc\n6Jn/HMC9qroFwK8D+LSIXOfAcYkcNVcsYjSdxvzQEOaHhjCaTmOuWESxWMTFizcA2A4gjeqfhbkd\nauyUNbIkkhxlZp3cXm4AvgbgfS3ud2h1X6LelctlHUkmtby8ULmWAR1JJnV6eloNY7JhDfPqzTAm\nNJfLdTymlfXPy+WyTk9Pazx+uwKLrq2dXi6XNZfLaS6X41rpAQKT65k7mjMXkQ0AkgB+4ORxiewq\nFovIlEqrF5stlQDA0mqJVvacXO6Nv4hSaReAewHMLT33woV3I5/P93RtZvBTQPg5VpooIq8HMAFg\nv6r+tNVjxsbGlr7OZDLIZDJOnZ5Crp/rl9QHQYeHe9vrs1KpoFIpmz5Pq93jgdsAjAKo3nf5suKO\nO/4UJ0581va2cfXXrFKp4K67HsXZs4eWzhulXeuDJpvNIpvN9v5EM933bjdU3xS+hWog57Zx5KjZ\nQkFHkkmdNAydNAwdSSZ1tlDo6Rjlcln3JRI6DWiulmKpp1nqKYde0hCFwqwmEvtU5E7TaZZcLtcy\nnVPdMi5XO86IAou20y3L26dN6sDAk7V2zvaURiJ/gMk0i1PB/FEAX+nymH5fM4VQp1x3L8GuUJjV\nTfFP6hp5XK/Go7pBdujtG7f0/KZQb9Nyrny2FoBPqsgxTSQ+rYXCbMs3hvbB/IQCf6LAvqWAayfQ\ntsvlV9tZZjAPGLPB3InSxOsBfBTAe0WkKCIFEbnJ7nGJgM657m6VJnX19MbzpYfwc/0ofoY78aI+\niwvGDdicSFhq03KufAuqKZK3Yu3al/EXf/G7ANAyP91uJyORpwDcAOBQ7Xj2tMvlA0MA6q9ZsHeF\notVs58xV9XsArnKgLUR90S64XbyYQbFYdGDp2hiANGKxFwFgVV68MT+9Ojd/Cq+9djVKpTQaZ6BW\nA+2tNtu1ksjPsHbt/0As9qKpMQEKFv4mybeqA4wVPLluHX7eeD+A0/G4Z73KTnuFAuhY4VJf22Vq\nagOmpjagUPhPOHHifkcX72rXvq1b/w5TUzfUznvI9gAr+QvXZiHXmalMmSsWcXh4GJlSCZVKBcdF\nsKNSwbqrrkJ240bsPXIEW0wG834sXbu83dty9cuRI3tRqVy2tIFFp9fESiVPu/ZZCeDcCclbZtdm\ncWyyULcbOABKurLKwjAmNZkc0UJhdsVj2g16fjIe1+npaUtVHsvnnVDDmNBEYt+q87bSqcKl1c+s\nTiRqd9xc7lzX18tK280y8/ui/oKb1SymTsRgHnlmA10ul9NJw2gu+dAJw7BVfdFrcLMayKy+caw+\n54QODt6qwDnXZok2cuKNiexjMCffaVea11wi169g3gu7gcxKr9hvJYVmf1/UX2aDOZNf5DupVArZ\neLxp+K466JlIJFxZZdDKVP1GsVgM6XQa6XTadI65fUnhDiyXFBK1xmBOANxZirVTFUhjkAaAPePj\nGE0mMWkYmDQM7E8kMPQf/gjbt98bwfVFGgsH3KsP7/T7Yn26D5npvjtxA9MsvuXmIFerfPLJ4xMt\np+s3pioWFxddzd96kS9ud87BwVt1cPDJnvPvTrCT/ydnwGSahaWJEefFjvONpW6JRAL3bt+OgzMz\nDWcHRpNJHMznl86fz+ctlfzZYba8r7l0r/pca6V8rc75yCN3A/iZpeM5gaWJ3jJbmshgHnFeBElg\nOUCcP38eA3ffjdtee23FzycNAxumppbO73U7gdaBbDn4ZgAA69Z9DcAAXn65uqJFPJ7F+Pienuq7\nGTypkdlg7tgSuERmNU4IWlup4OtXrmAzOq9KUs3fHsXMzE70e9p7o/pAZiurl7StoFQ6heoaK9aX\nmu10zubzM+hTHX/7Eef2IFelUsHh4WEcnJnBroUFfOjyZXxVFX/e0IJW0/Xra447Oe3drtXVJ0VU\nF8yyVgHT27m52YRX/LpvK3vmEWd1Ywar2q2C+Osi+PLatfi1WKw6XX98fNX56+uaLPdGDy09Jkq9\n1FabXHCzCXc0p9Xi8aM9p9H6xswoqRM3sJrF19zaH7LdhKCThqGPPfaYpfN3qsbp53Wtrj4p19Yk\nX10Bs7i46Fg7OJnHG17NiAVngJIfObXZROPx2v2B2VnXxKzm0r2NG+/UePyuFaV8x4//laPtsBvM\nubGzNV69iTKYk2/Vt4GbMAydMAzdl0hY2vFHtdMf2EmNx29fFeTj8U/q4uKio9fTHBzt1MebCbR2\neohcOMs6BnMGc2rBqd5huz+wgYEndGDgwVX3Ayc0Hr/dtQDWSwDoJdBamczDhbPsYZqFwZxMshLg\nFxcXNR7/ZMse+ODgyRbBfEKBaU0k9un09LQrYwRmgrmVQNHr68Vcu31ezIg1G8w57E2OsVKyVX/O\nsWMnsW3b/p5K7YrFOWzffi/m57dC5OMQOY6BgZNIJPbj+PH92LRpCs0ll8BpAAM4d+7HGBp6se9l\nfWZLP60s7GVlMS+yZ/VOUT7asclMxO92A/AIgFcBnOvwmL6+e5G36nnw5vVVOqn3cgYHT6rInT33\nSldXkkxrPH77Uk68UJit9dpP1Hrk+7S6Nri7H5XN9Obc6DUzzRJMcDPNAuDdAJIM5tFkpUJlZWDJ\nKdBbIDMb/KppmNsVmG4414TrqYZuKRG3Ai0Xzgoes8HckUlDqvpdEXmLE8ei4Gk3EWhHqYRisdhy\nanrrtILz1qxZgxMnPlub6HEJlcoLuHLlGlT7F+7pNkXf7uQts5OmOk28omDjb9EhXkzx9eu04t6l\nAGTRy5ICvSxDsDLPeQO2bv3bns7VCzu/E6v52F6n9jPXHlJmuu9mbgDegi5plgMHDizdTp061d/P\nJi6yki8O4jnbsZ9mUQVmFdinIsfUME6a+vhvNWXQr1SDFzXc/UzPuDG5iBOYVjt16tSKWAm3SxPN\nBPMwcnpGY/OxW/1H7+c5rbIyEag5qG7d+ml9/PEnet4300owcDqIeDW42K+BUzfemDiByRwvgvkG\nAM91+Hm/r9kRVmp3+7H5cKeetx82PG7F6ibGYeiZeVXD3Y/zuvHGxMoa88wGc0cSZiJyHMDfAoiL\nyCUR+YQTx3XbXLGI0XQa80NDmB8awmg6jTmHly41o3mZ2F0LCzg4M4PDw8O+zo1bycUyf2tPP5Yw\ntruZtV/OETWO/PWo6m5V/ZequlZV16vqESeO6yarAbTTTvJ2/pg6VYeYPWd4Bkj9z6vNj/24zjt5\nxEz33YkbfJ5msZO6cHLhKLNt6XZOPw2QRoWXNdxOpquYZvEXcG2W3tjNQzv9x2RmgNOLAdKw5Lj7\nJSyvjxtvTJzAZI7ZYM4NnWsqlQpG0+muu8S7pb5P5o5SCQCqu+8cOYItJj6y5/N5zA8NYdfCwor7\nmzdJttqmTL1N8Tj2jI+bahMFjxu7N0VphyirzG7ozGDewE4A7Ydu/9Hb/bwfwdxvb3ZEUcFgblFQ\negqdesn9CLxOvUEE5fUl8guzwZwbOjfptoaGHzRW3tRD4c6ZGYwODy8F6z3j4xht/pTRYpNkNzW/\nAR1lmobIMeyZe8Bu79RsL9nJXrDd3r4TnxbYq6coMtsz51+Dy9ycmOTkhJyl3n4yiUnDwKRhYH8i\ngT0me/vdaue78cuELiLfMlPy4sQNPi9NdINTJYNers1itfTOTumnH9eiIXIL3JzOT+bY7Z0uPcdm\nL9kOq719OzNlnXrdiMKMA6ABtSWVwsF8fimYHfJ5Dtmvg7JEYcG/Ihf1Yx2XIKm/AW2YmsKGqSkc\nKhRMVbJE/XUjMoPVLC5zamJS1GZj+m1CF5FbOGnIx+yW2EV1NiZLEymKGMxDrF9rr7TCAErkLdaZ\nk21maru5ZjqRPzCYB5AbA4JmNuvgRB4i/2CaJaD6PSDYLZWTSqUimbcnchsX2go5r+vMu03k8fti\nZURh49SGzjeJyAURKYnI/U4ck7rrdTZmL/lt1nYTBYvtYC4iMQD/BcAHAGwB8BERuc7ucclZvea3\nuy0ZwGBP5C+2c+Yi8q8AHFDV36h9//uoLgzzJ02PY87cI3bq0juVJjqVt2f540p8PaiRa3XmIvJB\nAB9Q1btr398B4J2qek/T4xjMXdIcDIrFYt/q0u0GnqjNZO2mWJzD8PBhlEoZAEA8nsX4+B6kUls8\nbRd5x5cDoGNjY0tfZzIZZDIZN08fCa1283nPfffhqj6dz87OTGZ2TIqSSqWC4eHDmJk5iHoGdGZm\nJ4aHR5HPH4zc6xFV2WwW2Wy25+c5lWYZU9Wbat8zzeKRdumU/YkEAODQ2bO+KiN0cyZrEOTzeQwN\nzWNhYdeK+w1jElNTGyL3elCVmz3zMwCuFZG3AHgFwIcBfMSB41KP2pULZi5eRPmhhzD65S9z+Vmi\nkLL9l6yqZQD7ADwNYA7ACVU9b/e45Kxfu+46S8vP9hMrYlZKpVKIx7NA0ysSj5+O5OtBveEM0BDp\nV9VKr23o5Thc2nal5QHQHQCAjRuzOHJkLwdAI4yrJkaUleDYraLEbIC2WpniRilekMr9gtRW6j8G\n8wjrJRh0682fP3vWVID2yxrrra6d5Y8UZGaDedcdn526VU9FfpPL5XTSMJZ2va/fJgxDp6endSSZ\n1HLD/WWgel+5bPo4uVyu53aVy2XN5XKay+VWnaudQmFWk8kRNYxJNYxJTSZHNJc7Z/oaiPyoFju7\nxlh+fgu4fq4n/vzzz3dcTKtfrCyt21ijvbCwCwsLuzAzcxC7dx/C0PPPu34NRG5jMA8wJ9YT71RR\nsmnTJkeO00slhpl11FspFou1WZMrw/alS+/HPzC9RxHAYB5QvQa9Tj34d993H3bH4zg5OLhiQa10\nOm06QHdbmMusbkvr9ioWiyG/fj3LHyn0uJ55QPWynnirKf57xscBYOn+DwH45jXX4AOf+xwOfeQj\nSwF4z/g4RpurY9oEaC/XWK/WaB/FzMxOoGEINh6fwgMPH8fopz7FCVMUbmYS607cwAFQR5kdcCyX\nyy0HAPclErovkTA1MGhlMNKqdu01M2C5PAA6oYYxoYnEPi0UZl2/BiInweQAKEsTA8psKWC79U8e\nHBjAWwF86PLlFff7YV0UOxOJWKNNYePLVRPJOUs5apMpkCCxk66xs4ojUZCxZx5w3XqiVlZS/MqZ\nMzh79mzbYzrRLiIyhzNAaUm7tAWAVfffeP/9+JsHH7Q1W5IzLomcw2BOK7TrKTfen0gkcO/27bam\n5PtlWj9RWDCYU8+c2CyCG04QOctsMGc3iYgoBBjMaYkTU/K54QSRN5hmoRWc2CyCG04QOYc5c7LM\nibJCliYSOYPBnIgoBFwZABWR20RkVkTKIrLNzrHIH/q5PjoR9Y/dz77PAbgVwGkH2mIbA5E9TqyP\nbgd/f0TW2Qrmqvq8ql4E0H1/uj7zOhAFndVNIZzS6ffHIE9kgpmlFbvdAJwCsK3LY+ytA9mBnWVT\nqcrpPTx70WmZ3nO5nI4kkzppGDppGDqSTOpsodDX9hD5CUwugdt11UQReQbAmxvvAqAAHlDVv+7l\njWNsbGzp60wmg0wm08vT2+plowbyn3a/v3edPYsv7dqFr166tPSznTMzGB0e5tIAFFrZbBbZbLbn\n53UN5qp6o5UGtdIYzMlfUqkUjsbj2Nm0psrpeBy3ulAf3qrO6R8B3PTSSyvaUwSw7sIF5PN5bN++\nve/tInJbc0f385//vKnnOdm18SxvHvZZh3Zyxmaf69QenlakUil8c926Vb+/IoA1tXLWOQCjAOYB\nbLh8GYfvuINjIkSNzORi2t0A7ATwEoDXALwC4JsdHtvXvNJsoaAjyaROGIZOGIbuSyRCkVutX5eV\nnLGV53q1vdqTjz+ud4roBKATgO4D9Bygd4roIqAjtTw6x0QoahDFbePCNuvQznKyQVuKtlKpYP+2\nbfhYbbOM+uepj8fjuKKKD168iH/T9ByuxEhREMlVE+tbhqXTad8FKyu6Dez267leiMVi2HvkCB5L\nJvGiYeCpWprn/hMncN+xY5CBAa+bSORrwY94tEqlUsH58+fxQqWCIFVl1/f+3DA1hQ1TUzhUKGBz\nbXu7b69f7+mYCGvdye8YzH3MysBuffLN4J49WHflCvajOnho5rl+0Pjp6vzZsxhNp/FSJoOt8/O4\nbXAQJwcGXB2cBTghjQLCTGLdiRv6PAAaVr0M7LabfHOniD45ONjzoLBXg6H1czdfyyKgt8fjOj09\n7Vp7OCGNvAanJg2Rt+qph3qe+1CHgd12efLfWrsWVx56CId27zbdk23elPmoy5syt7qWNQA+9PLL\niMViro2JcEIaBQWDeQDUUw9WXRWLYfPmzaYDYOM6LZx5SRQM/KsMEacmT/mhEsYvE8H80g6ibtgz\nD5GlWZzNW7a5NFDoJL9ci1/aQdRNqCYNUZXdyVN+mnDkl4lgfmkHRQ+3jfOJoAYBbspM5A8M5j7Q\nXBGSdbkixK6gvhERhQmDucf8lKrwI75REJkTybVZ/MQPFSF+xRmVRM5jNQu5ijXsRP3Bv5w+CWJ9\nshuLSfETC1F/MJj3iZc791jB1AdRsHEAtM+CMNDn5mAtB4aJesNqFjItn89jfmgIuxYWVtzfr518\nWMNOZJ7ZYG5rAFREHgTw2wCuAHgBwCdU9Sd2jhlFQei9d9PLNfSyEiQRmWP3L+hpAFtUNQngIoA/\nsN+kaPFDrtruYK2VawjbFn9EXnMszSIiOwF8UFXvbPNzplma+Cl/bDX14adrIAoj13PmIvJ1ACdU\n9XibnzOYN3E7V92NlXSP366BKGwcy5mLyDMA3tx4FwAF8ICq/nXtMQ8AWGwXyCkY7G6CQUTe6RrM\nVfXGTj8XkY8DuBnAe7sda2xsbOnrTCaDTCbT7SmhlkqlcDQex86mFMXpeBy3BqSyIwzXQOQn2WwW\n2Wy25+fZSrOIyE0A/hTAkKr+ny6PZZqlhTCU6YXhGoj8ypWcuYhcBHA1gHog/76q/l6bxzKYtxG1\n0kQiMo+ThoiIQoBL4BIRRQiDORFRCDCYExGFAIM5EVEIMJgTEYUAgzkRUQhwD1CKLNbGU5jwfy9F\nkh+WHiZyEicNUeRw2V4KEk4aImqjWCwiUyqt+M8fA7CjVFpKuxAFDYM5EVEIMJhT5NjdJo/Ij5gz\np0jisr0UFFw1kagLliZSEDCYExGFAKtZiIgihMGciCgEGMyJiEKAwZyIKARsBXMR+Y8iclZEiiLy\nLRH5ZacaRkRE5tntmT+oqglVTQH47wAOONAm12SzWa+bsIof2wT4s11skzlsk3l+bZcZtoK5qv60\n4dvXASsm1fmeH39xfmwT4M92sU3msE3m+bVdZthez1xE/hjAxwD8XwA32G4RERH1rGvPXESeEZFz\nDbfnav/+NgCo6h+p6noAxwCM9LvBRES0mmMzQEXkGgDfUNV3tPk5p38SEVlgZgaorTSLiFyrqv+z\n9u1OAOftNIaIiKyx1TMXkQkAcVQHPucB7FXVVxxqGxERmeTaQltERNQ/rs4A9eMkIxF5UETOi8iM\niEyKyBt80KbbRGRWRMoiss3jttwkIhdEpCQi93vZljoReUREXhWRc163pU5E1onIsyIyVysSuMcH\nbVorIj+o/b09JyK+mQciIjERKYjI171uCwCIyIsNsWna6/YAgIi8UURO1uLTnIi8q+Pj3eyZi8jr\n67XpIjIC4O2q+m9da0DrNv1rAM+qakVEvghAVfUPPG7TJlRTV4cB3KeqBY/aEQNQAvA+AP8LwBkA\nH1bVC160p6Fd7wbwUwCPqupWL9tSV+uY/LKqzojI6wHkAfyOD14rQ1UXROQqAN8DcI+qeh6sROTf\nAUgDeIOq3uKD9vw9gLSq/rPXbakTka8COK2qR0RkDQBDVX/S7vGu9sz9OMlIVf9GVevt+D6AdV62\nBwBU9XlVvQjA60HjdwK4qKrzqroI4ASA3/G4TVDV7wLwzR8dAKjqj1R1pvb1T1EtBvhVb1sFqOpC\n7cu1qBY8eJ5XFZF1AG4G8LDXbWkg8NFaVbUMwXtU9QgAqOrPOwVywIPGi8gfi8glALsBfM7t83cx\nDOCbXjfCR34VwEsN378MHwQovxORDQCSAH7gbUuW0hlFAD8C8IyqnvG6TQD+DMBn4IM3lgYK4BkR\nOSMid3ndGABvBfC/ReRILR31kIgMdnqC48Hcj5OMurWp9pgHACyq6nG/tImCp5ZimQCwv+mTqCdU\ntVJbO2kdgHeJyNu9bI+I/CaAV2ufYgTef/qsu15Vt6H6ieHTtVSel9YA2Abgv9batQDg97s9wVGq\neqPJhx4H8A0AY063oVm3NonIx1H9Jb63322p6+F18tI/Aljf8P262n3UQi2vOQHgMVX9K6/b00hV\nfyIipwDWprBPAAABfElEQVTcBOCHHjblegC3iMjNAAYB/IKIPKqqH/OwTaiXVKvqP4nIU6imGL/r\nYZNeBvCSquZq308A6FiA4HY1y7UN33acZOQWEbkJ1Y98t6jqFa/b04KXPZczAK4VkbeIyNUAPgzA\nF9UH8Fevrm4cwA9V9ZDXDQEAEXmTiLyx9vUggBsBeDogq6p/qKrrVfVtqP5/etbrQC4iRu0TFUTk\ndQDeD2DWyzap6qsAXhKReO2u96HLm7DjPfMuvlhr3NIkI5fP38p/BnA1qvkyAPi+qv6elw0SkZ21\ndr0JwH8TkRlV/Q2326GqZRHZB+BpVN/4H1FVP7wBHweQAfCLtfGXA/WBIg/bdD2AjwJ4rpajVgB/\nqKrf8rBZvwLgaK0qKQbgCVX9hoft8as3A3iqtuTIGgDHVPVpj9sEAPcAOCYi/wLA3wP4RKcHc9IQ\nEVEI+KYUh4iIrGMwJyIKAQZzIqIQYDAnIgoBBnMiohBgMCciCgEGcyKiEGAwJyIKgf8PNJwDyCaS\nVSAAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1081f7c10>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import pylab as plt\n",
    "%matplotlib inline\n",
    "N = 100\n",
    "D = 2\n",
    "\n",
    "x1 = np.random.multivariate_normal([0,0],[[1,0],[0,1]],50)\n",
    "x2 = np.random.multivariate_normal([2,2],[[1,0],[0,1]],50)\n",
    "x = np.vstack((x1,x2))\n",
    "\n",
    "plt.figure()\n",
    "plt.plot(x1[:,0],x1[:,1],'ro')\n",
    "plt.plot(x2[:,0],x2[:,1],'bo')\n",
    "\n",
    "x1test = np.random.multivariate_normal([0,0],[[1,0],[0,1]],200)\n",
    "x2test = np.random.multivariate_normal([2,2],[[1,0],[0,1]],200)\n",
    "\n",
    "testx = np.vstack((x1test,x2test))\n",
    "\n",
    "np.savetxt('trainx.csv',x,delimiter=',')\n",
    "np.savetxt('testx.csv',testx,delimiter=',')\n",
    "\n",
    "traint = np.hstack((np.zeros((50,)),np.ones((50,))))\n",
    "testt = np.hstack((np.zeros((200,)),np.ones((200,))))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following function computes the predicted class for a single test point. It computes the distance between the test point and all of the training points. These distances are then put into tuples with their class and the list of tuples is sorted by distance. The classes of the closest points are then used to vote for class 0 or 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def KNN_predict(X,t,testx,K):\n",
    "    di = []\n",
    "    for i,x in enumerate(X):\n",
    "        dis = ((x-testx)**2).sum()\n",
    "        di.append((dis,t[i]))\n",
    "    di = sorted(di,key=lambda di:di[0])\n",
    "    vote0 = 0\n",
    "    vote1 = 0\n",
    "    for k in range(K):\n",
    "        if di[k][1] == 0:\n",
    "            vote0 += 1\n",
    "        else:\n",
    "            vote1 += 1\n",
    "    if vote0 >= vote1:\n",
    "        return 0\n",
    "    else:\n",
    "        return 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Look over different values of $K$ and compute the accuracy of the classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "max_k = 50\n",
    "accuracy = np.zeros((max_k,))\n",
    "for k in range(max_k):\n",
    "    test_predict = np.zeros((400,))\n",
    "    for i,tx in enumerate(testx):\n",
    "        test_predict[i] = KNN_predict(x,traint,tx,k)\n",
    "\n",
    "    accuracy[k] = (test_predict == testt).mean()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plot the accuracy as a function of $K$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x108dc69d0>]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYEAAAEACAYAAABVtcpZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucVXW9//HXG5W8Y3kBhbyUqamlaZFpJ3ZqOnmJTvkw\nsLxlhp7oaomYPZxKM7IsT9Y5kfw8VirmFUxL8LJVMmVUBC+DUOjETRJB0lIZmM/vj+8aZzPumdnD\nbPbMsN7Px2MezLp913ct9qz3Xt/vuigiMDOzfBrQ2xUwM7Pe4xAwM8sxh4CZWY45BMzMcswhYGaW\nYw4BM7McqygEJNVJmitpnqRxZaZvJ+lmSbMlPSRp35Jpz2XjZ0maWc3Km5lZz6ir+wQkDQDmAUcA\nS4AGYFREzC2Z50fAyxHxfUl7A7+IiCOzaQuAgyNi5QbaBjMzW0+VnAkMB+ZHRFNENAOTgZHt5tkX\nuAcgIp4Bdpe0YzZNFa7HzMxqrJKD81BgYcnwomxcqdnApwAkDQd2BYZl0wKYLqlB0pk9q66ZmVXT\nplUq54fA5ZIeA54AZgFrs2mHRcTS7MxguqTGiJhRpfWamVkPVBICi0nf7FsNy8a9ISJeBj7fOizp\nWWBBNm1p9u8Lkm4hNS+9KQQk+SFGZmbdFBHqyfKVNAc1AHtK2k3SQGAUMLV0BkmDJG2W/X4mcF9E\nvCJpS0lbZ+O3Ao4CnuxoRRHhnwguvPDCXq9DX/jxfvC+8L7o/KcaujwTiIi1ksYC00ihMSkiGiWN\nSZNjIvBu4GpJLcBTwBnZ4oOBW7Jv+ZsC10TEtKrU3MzMeqyiPoGI+BOwd7txvyr5/aH207PxzwIH\n9rCOZma2gfjSzT6oUCj0dhX6BO+HNt4XbbwvqqvLm8VqRVL0lbqYmfUHkogadAybmdlGyiFgZpZj\nDgEzsxxzCJiZ5ZhDwMwsxxwCZmY55hAwM8sxh4CZWY45BMzMcswhYGaWYw4BM7MccwiYmeWYQ8DM\nLMccAmZmOVZRCEiqkzRX0jxJ48pM307SzZJmS3pI0r6VLmtmZr2ny/cJSBoAzAOOAJaQ3jk8KiLm\nlszzI+DliPi+pL2BX0TEkZUsW1KG3ydgZtYNtXqfwHBgfkQ0RUQzMBkY2W6efYF7ACLiGWB3STtW\nuKyZmfWSSkJgKLCwZHhRNq7UbOBTAJKGA7sCwypc1syM1au7v8zrr0NHDQjrU97q1R2X19zc/fL6\ng4peNF+BHwKXS3oMeAKYBaztbiH19fVv/F4oFPwuUbMceO01+OY34X//F448Ek49FT75Sdhii/Lz\nNzfDn/4EV18Nf/gDHHssTJoE222Xpq9ZA/X18POfw7PPwtveVlk9HngATjoprf+ii9ad1tgIhxwC\nd9wBhx223pvaY8VikWKxWNUyK+kTOASoj4i6bPg8ICJiQifLPAu8B9i/0mXdJ2BWW//8J9x4I1x7\nLbz1rXDKKVBXB5tt9uZ5V62CL38Z3vMe+Na3Oi7zlVfga1+Djo5TAwbAEUekA+0HPwjz58OJJ8Je\ne8Hll8O996aD+8MPww47lC9j5UrYZ59UxsiR8IMfwNSpMHkyDB0Ko0enANl00xQQX/pS5/th7Vq4\n5BK44gr40Y/g3HNTecOHp+lr1sChh8Luu8Pjj6efLbfsvMxaqUafQCUhsAnwDKlzdykwExgdEY0l\n8wwC/h0RzZLOBA6LiNMqWbakDIfAeliwAK65BrbeOn2LGTy4t2tkfdHs2fDf/w0tLWl41Sq45x4o\nFNLBf/nydPD961/T5+iUU+DAA0GChgYYNSodvO+6C779bTjjjPLrOPHE9E35vPPSAb+9V19NB9ir\nr05lr1iRvnV/8YtpuNXy5fDSS+W3ZautYOed1x13660wZkzavnPOSQfyu++GcePgscfKl7NmDUyf\nng78LS0pDIcOhd//Hi68MC23xRYpZO69F6ZNg5NPhu23T4HVF9QkBLIV1QGXk/oQJkXEDyWNIX2r\nn5idLVwNtABPAWdExKqOlu1gHQ6BEmvXwn33pQ/cAQesO+2f/4Qbbkh/SI2N6Q/05ZfTH8KHP5y+\nIR1/PGy+ee/UHeChh9K3u0pPxTuzZk06YC1e3POySr3nPXDwwesefDakCHj00XRg2W+/6pf/4osw\ncyYcdRRssknb+AUL4D/+I30jbj14DhwIRx/95m/b8+fDb36TfgYNSsvdcAP8z//Apz8N8+bBiBEw\ncWL6jEH69n/llXDxxfDTn8LnPtd1XSNSXbfbDvbeuzrbv2hRCo7990/DLS3wjnfALbfA+97XNt/y\n5TBhQvrytOuucPrpKdQ2LWkcP/HENO2UU1L4PfpoGl6xIn1urrkmBSikfbZyZduZQy3VLARqIa8h\nsGYNPPdc2/CqVembyO9+B0OGpA/sdtulA/tee8F118Htt8NHP5rGHXNM+oOG9Md4880pHB5/PH2Q\nTzpp3W9NQ4eWb2tdsSI1CbQ/IEakD3i5g/lrr6X53/KWdcf/8Y/plHzQoFTfQw9dt7yFCyvrtFu5\nMp3iX3tt+gPcd9+ul6lUSwvMmJGC8pRT4Ljj2rZj881h2LD1Lzsi/Z+uzXrFXn8dbrstHVhXr04h\nPn58ajbpKICam6GpqbL1Pf10+j+/+27YZRfYaad0kBo6FP7xj/TN/Jxz4KyzKt+Glha4//7U9j5m\nDOyxR9u0hx9O++uSS1I7+pQpKSx+8pP0Ge1LvvtdeOGF1NQD6f/muOPSl6vzz0/NSuUsXw7vfW/6\nLFxwAXz+823Tbr8dxo5NZxu/+106e2r9P691M1E1QoCI6BM/qSr58fjjEV//esTgwRG77Rbxznem\nn333jTj33IinnkrzrV0bce+9EaedFvHhD0f8/OcRL7zQdflNTREXXxxx4IFtZb/jHRFvfWvEGWdE\n3HdfxKpVEVddFVEoRGy+eZpeXx/xt79FPPtsxPe+F7HnnmnaRz4SceWVES+9FDFjRsSZZ6aydt89\n4i9/aVvvww9H7LBDxJ//HDF1atq+Sy6JWLw44tJLI/bfP2Knndrq1NnPfvtFnH9+xNy51d//EREt\nLREPPBDxhS9EvOtdbevddtuIG2/sfnnPPRfx/e+nsnbeua28d70r7a8ZM9I6FyyIGD484vjjI5Yv\nf3M5f/1rxPvfHzFsWGX7acSIiF//Ov3frFmT6jB4cMQNN6RyvvOdHu+qN7njjrTeyy6LeP756pdf\nLc89F7H99hGvvpqGJ01KfxOvv971srffnv5WWlrePO2ccyJOOCHittsiVq+OGDky4pe/rG7dK5Ed\nN3t27O1pAdX66Ush0NQUsdde6Q+53M8hh0RccUX5P+DOPP98+qM58MCIt7894tvfjnjmmQ2zDR1Z\nvDhiwoQUNgMHpgPRjTdGvPZaRENDxNix6SC+/fYR//VfEQ89lKbdfHP6oL/lLRH77JMO7AsXRtxy\nSzqoX3ppOlgPGZIO/q3+/vcUXttsE3H66RHFYgq2vuzBB9NBdNmydcf/8Y8Ru+5a/jMxZEjaZ2ef\nnfZZuQNHqddfTweSIUPWDf3rr0/7//LLuy6jM/ffHzF0aAq4npSzMfjYxyKuvTb9Xe+wQ8ScOdVf\nxwMPpC9Ma9ZUv+zOVCME3BxUxje+kU7Hx48vP3327HRqf8cd8PGPp3bQ9h1VU6akZoxWK1akDraR\nI1MzTqFQvuOsViJSJ12509fm5jS9tZmp1L//nZqTSpsxmppS889jj6XT7i984c3ram4uX15fNW4c\n/O1vqT1cSu3Xxx6b/k87as/fYYfub+NTT6XP0u9+lzo8W1rg+utTX0VPvf56qk+t+jz6qsmT4de/\nTv0khUJqBqq2iHQJ6fjx6fLWVldfnfoaPvvZdedfsSI1p+23X+pr2Wab9Vuvm4Myr72Wmky66+67\nI155Zd1xL72UmjmamrpefuXKiAsuSN8Ep01rq8tXvpKaSa66KmLy5PRz660RL7/c/Tr2F6tXr9ss\n1N+9+mo6W7r22nS2NmRIxJQpG259a9akb5OrVm24deTVq6+mv+kPfCCiuXnDref669NZb6vrrktn\nY/vsE3HqqW1//w8+mJqAzzgj4hOfiBg0KOJzn4uYPr37ZxK4OSi56abUjltJO1+ra66JGDAgYsyY\ndcdfemnE6NHdW//dd0fssktq4z/ooIhPfSpixYrulWF9T0NDauraY4/U5m791803p76WDam5OX35\ne/jhdEzYcceI2bPTF83TT09hMH58+kyVfqFYtiziZz+LeN/7Uj/Q+PGpX64SDoHMWWelLbnrrsrm\nnzYt/Uf8+c+pbf7OO9P41avTf8Ijj3S/DsuWRZx8cuoryHsb7Mbksssifvzj3q6F9Rc//WnEoYem\nACgW1532m99EnHhi560Mc+ZEfO1rqe+pkuNINUJgo+gT2HPP1Ia6887ws591Pu+jj6a7Im++OV3W\nNn16ukZ4zpx06deVV6YbQ8zMuuvll9Nlp5dfDiecsH5lRKRLlO+/H975zs7n9X0CpGeDfOhD6Xrm\nT386XbNbriPsxRdTB9HFF8Mvf7lu583ZZ6dr3mfPhu99L11HbGa2Plpaen7Rx+jR6aa/009fd/zk\nyanD/9RT03CtHiXdp02fnh46dcAB6QqUxnYPpHjySfjUp9KdgzNmpJuXSgMA0m3jxWK68uWYY2pW\ndTPbCFXjqr8RI9ITA9r7zW86frDe+qrWU0R7zfTp6fZ1KX2Dv+22tjtLW1rS3aD/+Z9w1VXpDtZy\nttkmPXLhX//q3cs2zcwghcCEdo/Z/Ne/2r7IVlO/PuStXZueKXPkkWn4+OPTo2VbXX99ukb3ggs6\nDoBWBxyw7uMNzMx6yz77pJaJv/+9bdxdd8EHPtD1say7+nUIPPpo6gzeZZc0/NGPpg7eF19Mz2j5\n9rdTU0/eb5Yxs/5Fgo98ZN0modtua3toXzX16xCYPh0+9rG24c03h8MPT3fy/upXKU39Xhoz649K\n+wVaWtLVixsiBPp1n8D06elJfqWOOy7d2j9rVnr+t5lZfzRiRHoHBMAjj6Sn/HZ1yej66FdnAvPn\np+fdQHps8qOPph1V6thj0+WiRx+dHgVrZtYf7bdfatpeujT1dW6oS9f7zZnA6tXw/venh0CdcEK6\n5PPgg9NDt0oNGZI6gr/4xd6pp5lZNQwYkG5ove++1B/QelZQ9fVUMpOkOklzJc2TNK7M9G0lTZX0\nuKQnJJ1WMu05SbMlzZI0c30r2vqmqjlzUgD89rfp+v9yvv99ePvb13dNZmZ9w4gR6QVBCxemm2I3\nhEreMTwAmEd6T/ASoAEYFRFzS+YZD2wbEeMl7UB6r/DgiFgjaQFwcESs7GI9nd4x/J3vpEtCf/CD\nCrfMzKyfe+yx1OLxuc+lL77t1eqO4eHA/IhoiohmYDIwst08AbQ+EXsb4MWIWNNazwrX06n2VwKZ\nmW3sDjgg3RewIa4KalXJwXkosLBkeFE2rtQVwL6SlgCzga+WTAtguqQGSWeuTyVXrkzvUfXNXGaW\nJ5tskp4XtCFDoFodw0cDsyLicEnvJB303xsRrwCHRcRSSTtm4xsjYka5Qurr69/4vVAoUMgu8r/n\nnvSy7PYvNDcz29jV1bX9XiwWKRaLVS2/kj6BQ4D6iKjLhs8jPcN6Qsk8fwAuiYg/Z8N3A+Mi4pF2\nZV0IvBwRl5VZT4d9AmedlTqFv/GNbm2bmdlGrVZ9Ag3AnpJ2kzQQGAVMbTdPE3BkVqnBwF7AAklb\nSto6G78VcBTwZHcr6f4AM7MNo8vmoIhYK2ksMI0UGpMiolHSmDQ5JgIXAf8naU622LkRsULSHsAt\nkiJb1zUR0el9vDNmpJdjDx+ehhcsSA9S2n//9d1EMzPrSJ97qcxZZ6VHpT7wQLrj91e/SsFQ7vIo\nM7M82yhfKtPcnDqBjzkGmprcFGRmtiH1ucdGNDfDZz6TesSPPhr+8Y8Nd7u0mVne9ckQ2Gwz+MpX\nYMkSuPPOtvcFmJlZdfXJ5qDNNku/X3IJPPhg79bHzGxj1qdDQKr+S5XNzKxNnw4BMzPbsBwCZmY5\n5hAwM8sxh4CZWY45BMzMcswhYGaWYw4BM7Mc63MhsHq1Q8DMrFb6XAj4TMDMrHYcAmZmOeYQMDPL\nsYpCQFKdpLmS5kkaV2b6tpKmSnpc0hOSTqt02fYcAmZmtVPJi+YHAPOAI4AlpHcOj4qIuSXzjAe2\njYjxknYAngEGAy1dLVtSRkQE22wDixbBoEFV2T4zs41Wrd4sNhyYHxFNEdEMTAZGtpsngG2y37cB\nXoyINRUuuw6fCZiZ1U4lITAUWFgyvCgbV+oKYF9JS4DZwFe7sew6HAJmZrVTrTeLHQ3MiojDJb0T\nmC7pvd0t5MIL62lpgYsugo9+tEChUKhS9czM+r9isUixWKxqmZX0CRwC1EdEXTZ8HhARMaFknj8A\nl0TEn7Phu4FxpJDpdNmSMuK111KfwOrV1dk4M7ONWa36BBqAPSXtJmkgMAqY2m6eJuDIrFKDgb2A\nBRUu+wY3BZmZ1VaXzUERsVbSWGAaKTQmRUSjpDFpckwELgL+T9KcbLFzI2IFQLllO1qXQ8DMrLa6\nbA6qFUmxbFmw337wwgu9XRszs76vVs1BNeMzATOz2nIImJnlmEPAzCzHHAJmZjnmEDAzyzGHgJlZ\njjkEzMxyzCFgZpZjDgEzsxxzCJiZ5ZhDwMwsx/pUCKxe7RAwM6ulPhUCPhMwM6sth4CZWY45BMzM\ncqyiEJBUJ2mupHmSxpWZ/k1JsyQ9JukJSWskbZdNe07S7Gz6zM7W4xAwM6utLt8sJmkAcAVwBLAE\naJA0JSLmts4TET8GfpzNfxzwtYh4KZvcAhQiYmVX63IImJnVViVnAsOB+RHRFBHNwGRgZCfzjwau\nKxlWheuhuRkGDqxkTjMzq4ZKDs5DgYUlw4uycW8iaQugDripZHQA0yU1SDqzsxX5TMDMrLa6bA7q\npuOBGSVNQQCHRcRSSTuSwqAxImaUW9ghYGZWW5WEwGJg15LhYdm4ckaxblMQEbE0+/cFSbeQmpfK\nhsD06fVEQH09FAoFCoVCBdUzM8uHYrFIsVisapmKiM5nkDYBniF1DC8FZgKjI6Kx3XyDgAXAsIh4\nNRu3JTAgIl6RtBUwDfhuREwrs544//xgiy3ggguqsGVmZhs5SUSEelJGl2cCEbFW0ljSAXwAMCki\nGiWNSZNjYjbrJ4E7WwMgMxi4RVJk67qmXAC0am6Gbbdd300xM7PuqqhPICL+BOzdbtyv2g1fDVzd\nbtyzwIGVVsZ9AmZmteU7hs3McswhYGaWYw4BM7MccwiYmeWYQ8DMLMccAmZmOeYQMDPLMYeAmVmO\nOQTMzHLMIWBmlmN9KgRWr3YImJnVUp8KAZ8JmJnVlkPAzCzHHAJmZjnW50LAL5o3M6udPhcCPhMw\nM6udikJAUp2kuZLmSRpXZvo3Jc2S9JikJyStkbRdJcuWcgiYmdVWJe8YHgDMI71jeAnQAIyKiLkd\nzH8c8LWIOLI7y0qKHXcMnngCBg/uySaZmeVDNd4xXMmZwHBgfkQ0RUQzMBkY2cn8o4Hr1mdZnwmY\nmdVWJSEwFFhYMrwoG/cmkrYA6oCburssOATMzGqt2h3DxwMzIuKl9VnYIWBmVlubVjDPYmDXkuFh\n2bhyRtHWFNTdZVm9up4f/AAGDIBCoUChUKigemZm+VAsFikWi1Uts5KO4U2AZ0idu0uBmcDoiGhs\nN98gYAEwLCJe7c6y2bwhBS0tPd4mM7NcqEbHcJdnAhGxVtJYYBqp+WhSRDRKGpMmx8Rs1k8Cd7YG\nQGfLdrQuNwWZmdVWl2cCtSIpttoqeOWV3q6JmVn/UKtLRGvGZwJmZrXlEDAzyzGHgJlZjjkEzMxy\nzCFgZpZjDgEzsxxzCJiZ5ZhDwMwsxxwCZmY55hAwM8uxPhUCfsm8mVlt9akQ8JmAmVltOQTMzHLM\nIWBmlmMOATOzHHMImJnlWEUhIKlO0lxJ8ySN62CegqRZkp6UdG/J+Ockzc6mzexsPQ4BM7Pa6vL1\nkpIGAFeQ3hO8BGiQNCUi5pbMMwj4BXBURCyWtENJES1AISJWdrUuh4CZWW1VciYwHJgfEU0R0QxM\nBka2m+ck4KaIWAwQEctLpqnC9TgEzMxqrJKD81BgYcnwomxcqb2At0m6V1KDpJNLpgUwPRt/Zmcr\ncgiYmdVWl81B3SjnIOBwYCvgL5L+EhF/BQ6LiKWSdiSFQWNEzChXyMyZ9dTXp98LhQKFQqFK1TMz\n6/+KxSLFYrGqZSoiOp9BOgSoj4i6bPg8ICJiQsk844DNI+K72fCVwB8j4qZ2ZV0IvBwRl5VZT5x/\nfnDxxT3dJDOzfJBERKgnZVTSHNQA7ClpN0kDgVHA1HbzTAE+LGkTSVsCHwQaJW0paeusslsBRwFP\ndrQiNweZmdVWl81BEbFW0lhgGik0JkVEo6QxaXJMjIi5ku4E5gBrgYkR8bSkPYBbJEW2rmsiYlpH\n63IImJnVVpfNQbUiKSZMCM49t7drYmbWP9SqOahmfCZgZlZbDgEzsxxzCJiZ5ZhDwMwsxxwCZmY5\n5hAwM8uxPhUCftG8mVlt9akQ8JmAmVltOQTMzHLMIWBmlmMOATOzHHMImJnlmEPAzCzHHAJmZjnm\nEDAzyzGHgJlZjlUUApLqJM2VNC97n3C5eQqSZkl6UtK93Vm2lUPAzKy2KnnR/ABgHnAEsIT0zuFR\nETG3ZJ5BwIPAURGxWNIOEbG8kmVLyohFi4KhQ6u0ZWZmG7lavVlsODA/IpoiohmYDIxsN89JwE0R\nsRggIpZ3Y9k3+EzAzKy2KgmBocDCkuFF2bhSewFvk3SvpAZJJ3dj2Tc4BMzMamvTKpZzEHA4sBXw\nF0l/6W4hl15a/8aTRAuFAoVCoUrVMzPr/4rFIsVisaplVtIncAhQHxF12fB5QETEhJJ5xgGbR8R3\ns+ErgT8Ci7tatqSMeO214C1vqc6GmZlt7GrVJ9AA7ClpN0kDgVHA1HbzTAE+LGkTSVsCHwQaK1z2\nDW4OMjOrrS6bgyJiraSxwDRSaEyKiEZJY9LkmBgRcyXdCcwB1gITI+JpgHLLdrSuAX3qrgUzs41f\nl81BtSIp+kpdzMz6g1o1B5mZ2UbKIWBmlmMOATOzHHMImJnlmEPAzCzHHAJmZjnmEDAzyzGHgJlZ\njjkEzMxyzCFgZpZjDgEzsxxzCJiZ5ZhDwMwsxxwCZmY55hAwM8sxh4CZWY5VFAKS6iTNlTQve59w\n++kjJL0k6bHs54KSac9Jmi1plqSZ1ay8mZn1TJevl5Q0ALgCOAJYAjRImhIRc9vNen9EfKJMES1A\nISJW9ri2ZmZWVZWcCQwH5kdEU0Q0A5OBkWXm6+gVZ6pwPWZmVmOVHJyHAgtLhhdl49r7kKTHJd0u\nad+S8QFMl9Qg6cwe1NXMzKqsy+agCj0K7BoR/5b0ceBWYK9s2mERsVTSjqQwaIyIGeUKqa+vf+P3\nQqFAoVCoUvXMzPq/YrFIsVisapmKiM5nkA4B6iOiLhs+D4iImNDJMs8CB0fEinbjLwRejojLyiwT\nXdXFzMzaSCIiOmqKr0glzUENwJ6SdpM0EBgFTG1XkcElvw8nhcsKSVtK2jobvxVwFPBkTypsZmbV\n02VzUESslTQWmEYKjUkR0ShpTJocE4ETJJ0NNAOvAp/JFh8M3CIpsnVdExHTNsSGmJlZ93XZHFQr\nbg4yM+ueWjUHmZnZRsohYGaWYw4BM7MccwiYmeWYQ8DMLMccAmZmOeYQMDPLMYeAmVmOOQTMzHLM\nIWBmlmMOATOzHHMImJnlmEPAzCzHHAJmZjnmEDAzy7GKQkBSnaS5kuZJGldm+ghJL0l6LPu5oNJl\nzcys93QZApIGAFcARwP7AaMl7VNm1vsj4qDs56JuLmslqv0i6f7K+6GN90Ub74vqquRMYDgwPyKa\nIqIZmAyMLDNfubfbVLqslfCHPPF+aON90cb7oroqCYGhwMKS4UXZuPY+JOlxSbdL2reby5qZWS/o\n8kXzFXoU2DUi/i3p48CtwF5VKtvMzDaQLl80L+kQoD4i6rLh84CIiAmdLPMscDApCCpaVpLfMm9m\n1k09fdF8JWcCDcCeknYDlgKjgNGlM0gaHBHLst+Hk8JlhaQul23V0w0xM7Pu6zIEImKtpLHANFIf\nwqSIaJQ0Jk2OicAJks4GmoFXgc90tuwG2hYzM+umLpuDzMxs49Xrdwzn+WYyScMk3SPpKUlPSPpK\nNv6tkqZJekbSnZIG9XZda0XSgOyGw6nZcC73haRBkm6Q1Jh9Pj6Y433xdUlPSpoj6RpJA/OyLyRN\nkrRM0pyScR1uu6TxkuZnn5ujKllHr4aAbyZjDfCNiNgP+BDwpWz7zwPuioi9gXuA8b1Yx1r7KvB0\nyXBe98XlwB0R8W7gAGAuOdwXknYBvgwcFBHvJTVhjyY/++Iq0vGxVNltzy7NPxF4N/Bx4JeSuuxr\n7e0zgVzfTBYRz0fE49nvrwCNwDDSPrg6m+1q4JO9U8PakjQMOAa4smR07vaFpG2B/4iIqwAiYk1E\nrCKH+yKzCbCVpE2BLYDF5GRfRMQMYGW70R1t+yeAydnn5TlgPukY26neDgHfTJaRtDtwIPAQ8MbV\nVhHxPLBT79Wspn4KfAso7ajK477YA1gu6aqsaWyipC3J4b6IiCXAT4C/kw7+qyLiLnK4L0rs1MG2\ntz+eLqaC42lvh4ABkrYGbgS+mp0RtO+t3+h77yUdCyzLzow6O4Xd6PcFqcnjIOAXEXEQ8C9SE0Ae\nPxfbkb757gbsQjoj+Cw53Bed6NG293YILAZ2LRkelo3LjewU90bgtxExJRu9TNLgbPoQ4B+9Vb8a\nOgz4hKQFwHXA4ZJ+Czyfw32xCFgYEY9kwzeRQiGPn4sjgQURsSIi1gK3AIeSz33RqqNtXwy8vWS+\nio6nvR0Cb9xMJmkg6Wayqb1cp1r7f8DTEXF5ybipwGnZ76cCU9ovtLGJiPMjYteIeAfpc3BPRJwM\n3Eb+9sUyYKGk1kevHAE8RQ4/F6RmoEMkbZ51ch5BunAgT/tCrHt23NG2TwVGZVdP7QHsCczssvDe\nvk9AUh2/AQsNAAAArUlEQVTpSojWm8l+2KsVqiFJhwH3A0+QTukCOJ/0H/d7Uqo3ASdGxEu9Vc9a\nkzQCOCciPiHpbeRwX0g6gNRBvhmwADid1EGax31xIemLQTMwC/gCsA052BeSrgUKwPbAMuBC0rPZ\nbqDMtksaD5xB2ldfjYhpXa6jt0PAzMx6T283B5mZWS9yCJiZ5ZhDwMwsxxwCZmY55hAwM8sxh4CZ\nWY45BMzMcswhYGaWY/8ffttJyNOQEKgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1088f5f50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.figure()\n",
    "plt.plot(range(max_k),accuracy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
